package __回溯算法

import "sort"

/*
*
https://leetcode.cn/problems/combination-sum/

39. 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，
找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。
你可以按 任意顺序 返回这些组合。
  - 规则1: candidates 中的 同一个 数字可以 无限制重复被选取 。
  - 规则2: 如果至少一个数字的被选数量不同，则两种组合是不同的。
  - 规则3: 对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：
输入: candidates = [2], target = 1
输出: []
*/
var (
	res39  [][]int
	path39 []int
)

func combinationSum(candidates []int, target int) [][]int {
	res39, path39 = make([][]int, 0), make([]int, 0, len(candidates)) //声明数组
	sort.Ints(candidates)                                             // 排序，为剪枝做准备
	dfs39(candidates, 0, target)                                      //调用递归
	return res39
}

func dfs39(candidates []int, start int, target int) {
	//如果target正好被减为0了，说明符合要求的找到了符合要求的path
	if target == 0 { // target 不断减小，如果为0说明达到了目标值
		temp := make([]int, len(path39)) //创建临时数组
		copy(temp, path39)               //复制
		res39 = append(res39, temp)      //加入总结果数组
		return
	}

	//从start位置开始遍历每个元素
	for i := start; i < len(candidates); i++ {
		if candidates[i] > target { // 剪枝，提前返回  如果当前元素直接大于目标值，直接返回即可
			break
		}
		path39 = append(path39, candidates[i])     //路径添加当前元素
		dfs39(candidates, i, target-candidates[i]) //调用递归
		path39 = path39[:len(path39)-1]            //回溯操作
	}
}
